// use crate::six::randomized_partition;

// 1. 最小值和最大值
pub fn minimum(a: Vec<i32>) -> i32 {
    let mut min = a[0];
    for i in 1..a.len() {
        if min > a[i] {
            min = a[i];
        }
    }
    min
}
pub fn minimum_maximum(a: Vec<i32>) -> (i32, i32) {
    let mut min: i32;
    let mut max: i32;
    if a[0] < a[1] {
        min = a[0];
        max = a[1];
    } else {
        min = a[1];
        max = a[0];
    }
    let mut id: usize;
    let mut id_1: usize;
    for i in 1..(a.len() / 2) {
        id = i * 2;
        id_1 = id + 1;
        if a[id] < a[id_1] {
            if min > a[id] {
                min = a[id];
            }
            if max < a[id_1] {
                max = a[id_1];
            }
        } else {
            if min > a[id_1] {
                min = a[id_1];
            }
            if max < a[id] {
                max = a[id];
            }
        }
    }
    (min, max)
}

// 2. 顺序统计量——第 i 小的值
/*
pub fn randomized_select(a: &mut Vec<i32>, p: i32, r: i32, i: i32) -> i32 {
    if p == r {
        return a[p as usize]
    }
    let q = randomized_partition(a, p, r);
    println!("{:?}", a);
    let k = q - p + 1;
    if i == k {
        return a[q as usize];
    } else if i < k {
        println!("***** i < k *****");
        return randomized_select(a, p, q-1, i);
    } else {
        println!("+++++ i >= k +++++");
        return randomized_select(a, q+1, r, i-k);
    }
}
*/
// 3. 选择算法
// 快速排序---中位数作为基数
pub fn select_partition(a: &mut Vec<i32>, p: i32, r: i32, x: i32) -> i32 {
    println!("SELECT_PARTITION—— p: {}, r: {}, x: {}", p, r, x);
    let mut j = p;
    for i in (p as usize)..(r as usize) {
        if a[i] == x {
            a.swap(i, r as usize);
            break;
        }
    }
    for i in (p as usize)..(r as usize) {
        if a[i] < x {
            println!("SWAP {} ----> {}", j, i);
            a.swap(i, j as usize);
            println!("{:?}", a);
            j += 1;
        }
    }
    a.swap(j as usize, r as usize);
    println!("{:?}", a);
    println!("p ---> {} | q ----> {} | r ----> {}", p, j, r);
    j
}
// 找出中位数
pub fn medium(a: &Vec<i32>) -> i32 {
    println!("{:?}", a);
    println!("----MEDIUM-----");
    if a.len() < 6 {
        if a.len() % 2 == 0 {
            return a[a.len() / 2 - 1];
        } else {
            return a[a.len() / 2];
        }
    }
    let temp = a
        .chunks(5)
        .map(|v| {
            if v.len() % 2 == 0 {
                return v[v.len() / 2 - 1];
            } else {
                return v[v.len() / 2];
            }
        })
        .collect::<Vec<i32>>();
    println!("{:?}", temp);
    return medium(&temp);
}
// 选择算法
pub fn select(a: &mut Vec<i32>, p: i32, r: i32, nth: i32) -> i32 {
    println!("SELECT —— p: {}, q: {}, nth: {}", p, r, nth);
    let x = medium(&a.get((p as usize)..=(r as usize)).unwrap().to_vec());
    println!("THE X = {}", x);
    let q = select_partition(a, p, r, x);
    let k = q - p + 1;
    if nth == k {
        x
    } else if nth < k {
        select(a, p, q - 1, nth)
    } else {
        select(a, q + 1, r, nth - k)
    }
}
